בהינתן גרף לא מכוון קשיר עם משקל אי שלילי על הצלעות, האם ייתכן שבחירה של מעגל כך שכל צומת שנבחרה היא זאת שהמעבר אלייה מהצומת הקודמת נעשתה עם צלע בעלת משקל מקסימאלי? אם כן, מתי? אם לא מדוע?
תשובות
הוסף תשובה
|
לצפיה בתשובות
יולי 2018
כן, רק אם כל המשקלים המקסמאליים במעגל שווים. אחרת,
לא ייתכן, נניח בשלילה שיש מעגל כזה v1,v2,v3,...,vN,v1 ונגדיר W - צלע בעלת משקל מקסימום שמחברת 2 צמתים במסלול. עכשיו, מהגדרת מקסימאליות של של כל צלע במסלול:
W(v1,v2) <= W(v2,v3) <= ... <= W(vK-1,vK) < W(vK,vK+1) <= ... <= W(vN-1,vN) < W(vN,v1) explanation
כל צלע במסלול חייבת להיות מקסימאלית, מאחר שאם אנחנו נמצאים על צומת vi כלשהי והגרף לא מכוון אז בחירה W למעבר לצומת הבאה היה חייב להיות גדול או שווה לכל W אחר שיש.
בנוסף, יש (W(vK-1,vK) < W(vK,vK+1 אחד לפחות כי אחרת כי אחרת כל המסלול מורכב מצלעות עם משקל מקסימום.
מהאי שיוויון הזה ברור לנו כי (W(v1,v2) < W(vN,v1 וברור שזאת סתירה כי במקרה זה האילוץ היה מחייב לבנות את המעגל מ-v1 ל-vN ולא ל-v2 כפי שהנחנו.
ראיון לתפקיד 
